/*
https://leetcode-cn.com/problems/minimum-cost-to-hire-k-workers/solution/gu-yong-k-ming-gong-ren-de-zui-di-cheng-ben-by-lee/
 */
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Solution857 {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        List<int[]> list=new ArrayList<>();
        for (int i=0;i<quality.length;i++){
            list.add(new int[]{quality[i],wage[i]});
        }
        list.sort((a,b)->a[1]*b[0]-a[0]*b[1]);
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>((a,b)->b-a);
        int ans=0;
        double min=Double.MAX_VALUE;
        for (int i=0;i<quality.length;i++){
            if (priorityQueue.size()==k-1){
                min=Math.min(min,(ans+list.get(i)[0])*((double)list.get(i)[1]/list.get(i)[0]));
            }
            ans+=list.get(i)[0];
            priorityQueue.offer(list.get(i)[0]);
            if (priorityQueue.size()>k-1) {
                ans -= priorityQueue.poll();
            }
        }
        return min;
    }

    public static void main(String[] args) {
        System.out.println(new Solution857().mincostToHireWorkers(new int[]{3,1,10,10,1},new int[]{4,8,2,2,7},3));
    }
}
